
#include <algorithm>
#include "common.h"

using namespace std;

namespace {

bool inArea(vector<VectorInt> &image, int x, int y) {
    return x >= 0 && x < image.size() && y >=0 && y < image[0].size();
}

void fill(vector<VectorInt> &image, int x, int y, int orginColor, int newColor) {
    if (!inArea(image, x, y)) return;
    if (image[x][y] != orginColor) return;
    if (image[x][y] == -1) return;

    // 打标记避免重复
    image[x][y] = -1;

    fill(image, x, y + 1, orginColor, newColor);
    fill(image, x, y - 1, orginColor, newColor);
    fill(image, x + 1, y, orginColor, newColor);
    fill(image, x - 1, y, orginColor, newColor);

    image[x][y] = newColor;
}

vector<VectorInt> visited;
int fill2(vector<VectorInt> &image, int x, int y, int orginColor, int newColor) {
    // 在区域内
    if (!inArea(image, x, y)) return 0;
    // 已访问
    if (visited[x][y] > 0) return 1;
    // 颜色不同
    if (image[x][y] != orginColor) return 0;

    // 打标记避免重复
    visited[x][y] = 1;

    int surround =
    fill2(image, x, y + 1, orginColor, newColor) +
    fill2(image, x, y - 1, orginColor, newColor) +
    fill2(image, x + 1, y, orginColor, newColor) +
    fill2(image, x - 1, y, orginColor, newColor);

    // std::cout << x << "," << y << ":" << surround << std::endl;
    if (surround < 4)
        image[x][y] = newColor;

    return 1;
}


vector<VectorInt> floodfill(vector<VectorInt> &image, int sr, int sc, int color) {
    int orginColor = image[sr][sc];
    // fill(image, sr, sc, orginColor, color);
    visited = vector<VectorInt>(image.size(), VectorInt(image[0].size(), 0));
    fill2(image, sr, sc, orginColor, color);
    return image;
}

void Handle() {
    vector<VectorInt> image = {
        {1,1,1,1},
        {1,1,1,1},
        {1,1,1,0},
        {1,1,0,1}
    };
    floodfill(image, 1, 1, 2);
    for (auto &v : image) {
        std::cout << v << std::endl;
    }
}
}

void HandleFloodFill() {
    Handle();
}
